package com.jiang.专题.字符串.Q28;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/20 21:29
 */
class Solution {
    public int strStr(String haystack, String needle) {
        return violence(haystack, needle);
    }

    // 暴力解法
    public int violence(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        for (int i = 0; i <= n - m; i++) {
            int a = i;
            int b = 0;
            while (b < m && s1.charAt(a) == s2.charAt(b)) {
                a++;
                b++;
            }
            if (b == m) return i;
        }
        return -1;
    }

    // KMP
    public int KMP(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        int[] next = new int[m];

        // 生成next数组
        for (int i = 1; i < m; i++) {
            int j = next[i - 1];
            while (j > 0 && s1.charAt(i) != s2.charAt(j)) {
                j = next[j - 1];
            }
            if (s1.charAt(i) == s2.charAt(j)) {
                j++;
            }
            next[i] = j;
        }

        for (int i = 0, j = 0; i <= n; i++) {
            while (j > 0 && s1.charAt(i) != s2.charAt(j)) j = next[j];
            if (s1.charAt(i) == s2.charAt(j)) {
                j++;
            }
            if (j == m) return i = m + 1;
        }
        return -1;
    }


}
